class Solution {
public:
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
    	if ((m + n) % 2 == 0) {
			return (FindKthInTwoSortedArrays(A, m, B, n, (m + n) / 2) +
				   FindKthInTwoSortedArrays(A, m, B, n, (m + n) / 2 + 1)) / 2.0;
		} else {
			return FindKthInTwoSortedArrays(A, m, B, n, (m + n) / 2 + 1);
		}

    }

	int FindKthInTwoSortedArrays(int A[], int n, int B[], int m, int k) {
		pair<bool, int> result = FindKth(A, n, B, m, k, 0, n - 1 >= k - 1 ? k - 1 : n - 1);
		if (result.first) {
			return result.second;
		}
		result = FindKth(B, m, A, n, k, 0, m - 1 >= k - 1 ? k - 1 : m - 1);
		return result.second;
	}

	pair<bool, int> FindKth(int A[], int n, int B[], int m, int k, int low, int high) {
		if (low > high) {
			return make_pair(false, 0);
		}
		int mid = (low + high) / 2;
		int B1 = k - mid - 2 >= 0 ? B[k - mid - 2] : numeric_limits<int>::min();
		int B2 = k - mid - 1 <= m - 1 ? B[k - mid - 1] : numeric_limits<int>::max();

		if (m + mid + 1 >= k && B1 <= A[mid] && A[mid] <= B2) {
			return make_pair(true, A[mid]);
		} else if (A[mid] > B2) {
			return FindKth(A, n, B, m, k, low, mid - 1);
		} else {
			return FindKth(A, n, B, m, k, mid + 1, high);
		}
	}
};